class Solution:
    def missingNumber(self, nums: list) -> int:
        # 二分查找即可, 由于题目说有且仅有一个数字不存在, 所以不用担心数字不存在的情况
        i, j = 0, len(nums) - 1
        while i <= j:
            tmp = (i + j) // 2
            if nums[tmp] == tmp: i = tmp + 1
            else: j = tmp - 1
        
        return i

"""
只要是可以将数组通过某一个条件划分成两部分的题目, 几乎都可以用二分查找来解决.
"""



if __name__ == '__main__':
    solution = Solution()

    nums = [0,1,3]
    print("My:", solution.missingNumber(nums))
    print("Right:", 2)
    print("------")

    nums = [0,1,2,3,4,5,6,7,9]
    print("My:", solution.missingNumber(nums))
    print("Right:", 8)

    print("Done!")